﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Drawing;

namespace Hungarian_Matching
{
    public class Hungarian
    {
        private int _x = 0;
        private int _y = 0;
        private int[,] _matrix;
        private int[,] _sourceMatrix;
        private List<Point> _result = new List<Point>();

        public Hungarian(int xNum, int yNum)
        {
            _x = xNum;
            _y = yNum;
            _matrix = new int[_x, _y];

            _matrix[0, 0] = 2;
            _matrix[0, 1] = 10;
            _matrix[0, 2] = 9;
            _matrix[0, 3] = 7;

            _matrix[1, 0] = 15;
            _matrix[1, 1] = 4;
            _matrix[1, 2] = 14;
            _matrix[1, 3] = 8;

            _matrix[2, 0] = 13;
            _matrix[2, 1] = 14;
            _matrix[2, 2] = 16;
            _matrix[2, 3] = 11;

            _matrix[3, 0] = 4;
            _matrix[3, 1] = 15;
            _matrix[3, 2] = 13;
            _matrix[3, 3] = 9;

            _sourceMatrix = _matrix.Clone() as int[,];
        }

        /// <summary>
        /// 在各行/列中找出最小值,并减掉这个最小值
        /// </summary>
        private void Step1()
        {
            //找出每行最小值,并减掉这个最小值           
            for (int i = 0; i < _x; i++)
            {
                var x_min = int.MaxValue;
                for (int j = 0; j < _y; j++)
                {
                    if (x_min > _matrix[i, j])
                        x_min = _matrix[i, j];
                }

                for (int j = 0; j < _y; j++)
                    _matrix[i, j] -= x_min;
            }

            //找出每列最小值,并减掉这个最小值            
            for (int i = 0; i < _y; i++)
            {
                var y_min = int.MaxValue;
                for (int j = 0; j < _x; j++)
                {
                    if (y_min > _matrix[j, i])
                        y_min = _matrix[j, i];
                }

                for (int j = 0; j < _y; j++)
                    _matrix[j, i] -= y_min;
            }
        }

        /// <summary>
        /// 检查是否包含零完全指派
        /// 检查各行,对碰上第一个零,做记号,同行或者同列上的其他进行 x 标记 (由零减少的行先做)
        /// </summary>
        private bool Step2()
        {
            _result.Clear();
            bool[,] isDeleted = new bool[_x, _y];
            var zeroNodes = new List<ZeroNode>();

            for (int i = 0; i < _x; i++)
            {
                var zeroNum = 0;
                for (int j = 0; j < _y; j++)
                {
                    if (_matrix[i, j] == 0)
                        zeroNum++;
                }

                if (zeroNum > 0)
                    zeroNodes.Add(new ZeroNode(i, zeroNum));
            }

            //根据包含零个数对行进行排序
            zeroNodes = zeroNodes.OrderBy(z => z.ZeroNum).ToList();
            while (zeroNodes.Count > 0)
            {
                //并从零最少的行开始检验
                var node = zeroNodes.First();

                if (node.ZeroNum <= 0)
                    zeroNodes.RemoveAt(0);
                else
                {
                    //对碰当前行第一个零
                    for (int j = 0; j < _y; j++)
                    {
                        if (_matrix[node.X, j] == 0 && !isDeleted[node.X, j])
                        {
                            //保存当前第一个零,并从行列表中移除当前行
                            _result.Add(new Point(node.X, j));
                            zeroNodes.RemoveAt(0);

                            //删除与第一个零同列上的其他零
                            for (int i = 0; i < _x; i++)
                            {
                                if (_matrix[i, j] == 0)
                                {
                                    isDeleted[i, j] = true;
                                    var relatedNode = zeroNodes.FirstOrDefault(z => z.X == i);
                                    if (relatedNode != null)
                                        relatedNode.ZeroNum--;
                                }
                            }

                            break;
                        }
                    }
                }
                zeroNodes = zeroNodes.OrderBy(z => z.ZeroNum).ToList();
            }

            return _result.Count == _x;
        }

        /// <summary>
        /// 画出最少数目的垂直与水平线来包含所有的零至少一次
        /// </summary>
        private void Step3()
        {
            bool[,] isDeleted = new bool[_x, _y];
            for (int i = 0; i < _x; i++)
            {
                for (int j = 0; j < _y; j++)
                {
                    if (_matrix[i, j] == 0 && !isDeleted[i, j])
                    {
                        int x_counter = 0, y_counter = 0;

                        for (int ii = 0; ii < _x; ii++)
                            if (ii != i && _matrix[ii, j] == 0)
                                x_counter++;

                        for (int jj = 0; jj < _y; jj++)
                            if (jj != j && _matrix[i, jj] == 0)
                                y_counter++;

                        if (x_counter > y_counter)
                            for (int ii = 0; ii < _x; ii++)
                                isDeleted[ii, j] = true;
                        else
                            for (int jj = 0; jj < _y; jj++)
                                isDeleted[i, jj] = true;

                    }
                }
            }

            //找出未被画线的元素中最小值K
            int k = int.MaxValue;
            for (int i = 0; i < _x; i++)
            {
                for (int j = 0; j < _y; j++)
                {
                    if (!isDeleted[i, j])
                        if (k > _matrix[i, j])
                            k = _matrix[i, j];
                }
            }

            //将含有这些未被画线的元素对应的列所有元素减去K
            for (int i = 0; i < _x; i++)
            {
                for (int j = 0; j < _y; j++)
                {
                    if (!isDeleted[i, j])
                    {
                        for (int jj = 0; jj < _y; jj++)
                            _matrix[i, jj] -= k;

                        break;
                    }
                }
            }

            //如果有负值,则将对应的列加上K
            for (int i = 0; i < _x; i++)
            {
                for (int j = 0; j < _y; j++)
                {
                    if (_matrix[i, j] < 0)
                    {
                        for (int ii = 0; ii < _x; ii++)
                            _matrix[ii, j] += k;

                        break;
                    }
                }
            }

        }


        public void Run()
        {
            Step1();
            while (!Step2())
            {
                Step3();
            }

            for (int i = 0; i < _x; i++)
            {
                for (int j = 0; j < _y; j++)
                    Console.Write("{0,3}", _sourceMatrix[i, j]);
                Console.WriteLine();
            }

            Console.WriteLine();
            Console.WriteLine(" ------------- ");
            Console.WriteLine();

            for (int i = 0; i < _x; i++)
            {
                for (int j = 0; j < _y; j++)
                    Console.Write("{0,3}", _matrix[i, j]);
                Console.WriteLine();
            }

            Console.WriteLine();
            Console.WriteLine(" ------------- ");
            Console.WriteLine();

            var total = 0;
            var result = _result.OrderBy(r => r.X).ToList();
            foreach (var item in result)
            {
                total += _sourceMatrix[item.X, item.Y];
                Console.WriteLine("{0,3} = {1,2}", string.Format("({0},{1})", item.X, item.Y), _sourceMatrix[item.X, item.Y]);                
            }

            Console.WriteLine();
            Console.WriteLine("SUM: {0,5}", total);

            Console.ReadKey();
        }

    }

    class ZeroNode
    {
        public int X { get; set; }
        public int ZeroNum { get; set; }

        public ZeroNode(int x, int zeroNum)
        {
            this.X = x;
            this.ZeroNum = zeroNum;
        }
    }
}
